package 算法.图.无向图;

import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import com.sun.org.apache.xml.internal.security.Init;
import edu.princeton.cs.algs4.MinPQ;
import 算法.图.util.Edge;
import 算法.背包.Bag;

/**
 * 【最小生成树：Prim算法：延时实现】
 * 	
 * @Date   2017-09-03 16:22
 * @author Administrator
 * @version TODO:>>>>>>>尚未测试
 */
public class LazyPrimMST {
	private boolean[] marked;		//保存：已加入mst的顶点
	private List<Edge> mst;		    //最小生成树，存放mst的依次边
	private MinPQ<Edge> pq;			//优先队列，小谷堆，用于找出最短横边
	private EdgeWeightedGraph G;
	public LazyPrimMST(EdgeWeightedGraph G) {
		marked = new boolean[G.V];
		mst = new ArrayList<>();
		pq = new MinPQ();
		this.G = G;
		start();
	}
	
	private void start() {
		visit(0);                   //从0节点开始生成最小生成树
		while (pq.isEmpty()) {
			Edge edge = pq.delMin();
			int v = edge.either(), w = edge.other(v);
			if (marked[v] && marked[w])	continue;
			mst.add(edge);
			if (!marked[v]) 	visit(v);
			if (!marked[w])		visit(w);
		}//while
	}
	
	private void visit(int v) {
		marked[v] = true;
		for (Edge edge : G.adj[v])
			if (!marked[edge.other(v)])	pq.insert(edge);
	}
}
